#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int strangePrinter(string s) {
        int sLen = s.size();
        int **dp = new int *[sLen];
        for (int i = 0; i < sLen; ++i) {
            dp[i] = new int[sLen];
            for (int j = i + 1; j < sLen; ++j)
                dp[i][j] = sLen;
            dp[i][i] = 1;
        }
        for (int i = sLen - 1; i >= 0; --i)
            for (int j = i + 1; j < sLen; ++j)
                if (s[i] != s[j]) {
                    for (int k = i; k < j; ++k) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
//                        cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
                    }
                } else
                    dp[i][j] = dp[i][j - 1];
        return dp[0][sLen - 1];
    }
};

int main() {
    Solution solution;
    string s = "aaabbb";
    solution.strangePrinter(s);
}

